import random
import time

def insertion_sort(A):
    for j in range (1, len(A)):
        key = A[j]
        i = j-1
        while 1 > -1 and A[i] > key:
            A[i+1] = A[i]
            i = i-1
            pass
        A[i+1] = key
        pass
    pass

ficheiro = open("dados.dat", "w")
for N in xrange(1000, 15000, 1000):
    A = [ random.randint(0, 100) for k in range(N) ]

    t1 = time.clock()
    insertion_sort(A)
    t2 = time.clock()
    s = "{0} {1}\n".format(N, t2-t1)
    ficheiro.write(s)
    pass
ficheiro.close()